package com.zhangx.datastructure.hashtable;

/**
 * @ClassName MyHashTable
 * @Description 散列表
 * P365
 * @Author zhangx
 * @Date 2021/2/2 8:32
 **/
public class MyHashTable {

    MyHashTable myHashTable;

    int[] elem;
    int count;

    int m = 0;

    int init(){
        myHashTable = new MyHashTable();
        m = Constant.HASHSIZE;
        myHashTable.count = m;
        myHashTable.elem = new int[m];
        for (int i = 0; i < m; i++) {
            myHashTable.elem[i] = Constant.NULLKEY;
        }
        return Constant.SUCCESS;
    }

    /**
     * 除法散列法
     * @param key
     * @return
     */
    int hash(int key){
        return key % m;
    }

    void insert(int key){
        int addr = hash(key);
        while (myHashTable.elem[addr]!=Constant.NULLKEY){
            addr = (addr + 1) % m;//开放定址法，为了解决冲突，+1继续取模
        }
        myHashTable.elem[addr] = key;
    }

    int search(int k){
        int addr = hash(k);
        while (myHashTable.elem[addr]!=k){
//            发生了冲突
            addr = (addr +1) % m;
            if (myHashTable.elem[addr] == Constant.NULLKEY//找不到
                ||addr == hash(k)){//循环又回到了起点，证明找了一圈也没有,注意上面的+1，addr范围[0,addr]
//                没找到
                return Constant.UNSUCCESS;
            }
        }
        System.out.println(myHashTable.elem[addr]);
        return Constant.SUCCESS;
    }

    public static void main(String[] args) {
        int[] data = new int[]{12,67,56,16,25,37,22,29,15,47,48,34};
        MyHashTable h = new MyHashTable();
        h.init();
        for (int i = 0; i < data.length; i++) {
            h.insert(data[i]);
        }
        h.search(34);
    }
}
